package me.mingshan.leetcode;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * https://leetcode.cn/problems/path-sum/description/
 * <p>
 * 给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，
 * 这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。
 * <p>
 * 叶子节点 是指没有子节点的节点。
 *
 * @author hanjuntao
 * @date 2025/8/28 0028
 */
public class L_112_二叉树路径总和 {

    public static void main(String[] args) {
        TreeNode root = new TreeNode(5);
        root.left = new TreeNode(4);
        root.right = new TreeNode(8);
        root.left.left = new TreeNode(11);
        root.left.left.left = new TreeNode(7);
        root.left.left.right = new TreeNode(2);
        root.right.left = new TreeNode(13);
        root.right.right = new TreeNode(4);
        root.right.right.right = new TreeNode(1);

        //       1
        //      2  3
        //    4   5
        //  6   7
    }

    /**
     * 思路：
     * <p>
     * 从需求上看，需要遍历出所有路径，然后判断路径和是否等于目标值
     * <p>
     * 对于任何一个节点，其到叶子节点的路径和= 子树到叶子节点的路径和 + 当前节点的值
     * 所以每次遍历到一个节点，就让目标值减去当前节点的值 = val,判断子树的叶子节点和是否等于val
     *
     * 这明显是一个递归DFS,重要的利用了减法思想
     *
     * 递归终止条件：
     * 1. 如果当前节点为空，则返回false
     * 2. 如果当前节点为叶子节点，则判断路径和是否等于目标值
     *
     *
     * @param root
     * @param targetSum
     * @return
     */
    public static boolean hasPathSum(TreeNode root, int targetSum) {
        if (root == null) {
            return false;
        }

        // 叶子节点, 判断路径和是否等于目标值
        if (root.left == null && root.right == null) {
            return root.val == targetSum;
        }

       return hasPathSum(root.left, targetSum - root.val)
               || hasPathSum(root.right, targetSum - root.val);
    }

    /**
     * DFS 迭代版本
     *
     * @param root
     * @param targetSum
     * @return
     */
    public static boolean hasPathSum2(TreeNode root, int targetSum) {
        if (root == null) {
            return false;
        }

        Stack<TreeNode> nodeStack = new Stack<>();
        Stack<Integer> sumStack = new Stack<>();

        nodeStack.push(root);
        sumStack.push(targetSum);

        while (!nodeStack.isEmpty()) {
            TreeNode node = nodeStack.pop();
            int currentSum = sumStack.pop();

            // 检查叶子节点
            if (node.left == null && node.right == null && node.val == currentSum) {
                return true;
            }

            // 压入右子节点
            if (node.right != null) {
                nodeStack.push(node.right);
                sumStack.push(currentSum - node.val);
            }

            // 压入左子节点
            if (node.left != null) {
                nodeStack.push(node.left);
                sumStack.push(currentSum - node.val);
            }
        }

        return false;
    }

    /**
     * BFS
     *
     * 使用队列存储节点和对应的累计和
     * 从根节点开始，累计和为根节点值
     *
     * 处理队列中的节点：
     * 如果是叶子节点且累计和等于目标值，返回 true
     * 否则将子节点和更新后的累计值加入队列
     *
     *
     * @param root
     * @param targetSum
     * @return
     */
    public static boolean hasPathSum3(TreeNode root, int targetSum) {
        if (root == null) {
            return false;
        }

        Queue<TreeNode> nodeQueue = new LinkedList<>();
        Queue<Integer> sumQueue = new LinkedList<>();

        nodeQueue.offer(root);
        sumQueue.offer(root.val);

        while (!nodeQueue.isEmpty()) {
            TreeNode node = nodeQueue.poll();
            int currentSum = sumQueue.poll();

            // 检查叶子节点
            if (node.left == null && node.right == null && currentSum == targetSum) {
                return true;
            }

            // 处理左子节点
            if (node.left != null) {
                nodeQueue.offer(node.left);
                sumQueue.offer(currentSum + node.left.val);
            }

            // 处理右子节点
            if (node.right != null) {
                nodeQueue.offer(node.right);
                sumQueue.offer(currentSum + node.right.val);
            }
        }

        return false;
    }

}
